from typing import List

"""
原理：
如果全是大于等于0的元素，返回的结果也是按这个顺序排列
如果全是小于等于0的元素，返回的结果是按这个逆序排列

如果这两种情况都有：
使用双指针归并排序
"""


class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        if not A:
            return []
        p1 = 0
        for i, value in enumerate(A):
            if value < 0:
                p1 = i
            else:
                break

        p2 = p1 + 1
        res = []
        while p1 >= 0 or p2 < len(A):
            if p1 >= 0 and p2 < len(A):
                if -A[p1] > A[p2]:
                    res.append(A[p2] ** 2)
                    p2 += 1
                else:
                    res.append((-A[p1]) ** 2)
                    p1 -= 1
            elif p1 >= 0:
                res.append((-A[p1]) ** 2)
                p1 -= 1
            else:
                res.append(A[p2] ** 2)
                p2 += 1

        return res
